#include<iostream>
using namespace std;
const bool BLACK=true;
const bool WHITE=false;

class State{
	bool pieceOn;//true if the spot is taken; false otherwise
	bool colorIsBlack;//true if spot is taken by black; otherwise white
public:
	State(){
		Initialize();
	}
	bool getpieceOn()
	{
		return pieceOn;
	}
	bool getcolorIsBlack()
	{
		return colorIsBlack;
	}
	void setpieceOn(bool newpieceOn)
	{
		pieceOn = newpieceOn;
	}
	void setcolorIsBlack(bool newcolorIsBlack)
	{
		colorIsBlack = newcolorIsBlack;
	}
	void Initialize(){
		pieceOn=colorIsBlack=0;
	}
	void SetBlack()
	{
		pieceOn = true;
		colorIsBlack = true;
	}
    void SetWhite()
	{
		pieceOn = true;
		colorIsBlack = false;
	}
	void SetNone()
	{
		pieceOn = false;
		colorIsBlack = false;
	}
	bool PutPiece(bool black){
		if(pieceOn)
			return false;//error occurs
		pieceOn=1;
		colorIsBlack=black;
		return true;
	}
	bool Reverse(){
		if(pieceOn){
			colorIsBlack=(!colorIsBlack);
			return true;
		}
		else{
			return false;//error occures
		}
	}
	bool isOn(){
		return pieceOn;
	}
	bool isBlack(){
		return colorIsBlack;
	}
};

class Board{
friend class State;
public:
	Board(){
		for(int i(0); i<10; i++){//we only use 1 to 8
			for(int j(0); j<10; j++){//we only use 1 to 8
				board[i][j].Initialize();
			}
		}
		board[5][5].PutPiece(WHITE);
		board[4][4].PutPiece(WHITE);
		board[5][4].PutPiece(BLACK);
		board[4][5].PutPiece(BLACK);
		count[WHITE]=count[BLACK]=2;
	}
	void Reset()
		{
	for(int i(0); i<10; i++){//we only use 1 to 8
		for(int j(0); j<10; j++){//we only use 1 to 8
			board[i][j].Initialize();
			temp[i][j].Initialize();
		}
	}
	board[5][5].PutPiece(WHITE);
	board[4][4].PutPiece(WHITE);
	board[5][4].PutPiece(BLACK);
	board[4][5].PutPiece(BLACK);
	count[WHITE]=count[BLACK]=2;
}
	void copy(Board bd){
		for(int i(0); i<10; i++){
			for(int j(0); j<10; j++){
				board[i][j].setpieceOn(bd.board[i][j].getpieceOn());
				board[i][j].setcolorIsBlack(bd.board[i][j].getcolorIsBlack());
			}
		}
		count[0]=bd.count[0];
		count[1]=bd.count[1];
	}
	bool PutPiece(bool black, int x, int y)
	{
	if(board[x][y].isOn()){
		return false;
	}
	if(x==0||x==9||y==0||y==9){
		return false;
	}
	int successfullyPut(0), broke(0);
	int i;
	for(i=1; ;i++){
		if(board[x+i][y].isOn()&&board[x+i][y].isBlack()!=black){
			board[x+i][y].Reverse();
			count[black]++;
			count[!black]--;
			successfullyPut++;
		}
		else{
			broke++;
			break;
		}
	}
	if(broke&&!board[x+i][y].isOn()){
		broke--;
		for(i--; i>0; i--){
			board[x+i][y].Reverse();
			count[black]--;
			count[!black]++;
			successfullyPut--;
		}
	}



	for(i=1; ;i++){
		if(board[x-i][y].isOn()&&board[x-i][y].isBlack()!=black){
			board[x-i][y].Reverse();
			count[black]++;
			count[!black]--;
			successfullyPut++;
		}
		else{
			broke++;
			break;
		}
	}
	if(broke&&!board[x-i][y].isOn()){
		broke--;
		for(i--; i>0; i--){
			board[x-i][y].Reverse();
			count[black]--;
			count[!black]++;
			successfullyPut--;
		}
	}




	for(i=1; ;i++){
		if(board[x][y+i].isOn()&&board[x][y+i].isBlack()!=black){
			board[x][y+i].Reverse();
			count[black]++;
			count[!black]--;
			successfullyPut++;
		}
		else{
			broke++;
			break;
		}
	}
	if(broke&&!board[x][y+i].isOn()){
		broke--;
		for(i--; i>0; i--){
			board[x][y+i].Reverse();
			count[black]--;
			count[!black]++;
			successfullyPut--;
		}
	}




	for(i=1; ;i++){
		if(board[x][y-i].isOn()&&board[x][y-i].isBlack()!=black){
			board[x][y-i].Reverse();
			count[black]++;
			count[!black]--;
			successfullyPut++;
		}
		else{
			broke++;
			break;
		}
	}
	if(broke&&!board[x][y-i].isOn()){
		broke--;
		for(i--; i>0; i--){
			board[x][y-i].Reverse();
			count[black]--;
			count[!black]++;
			successfullyPut--;
		}
	}




	for(i=1; ;i++){
		if(board[x+i][y+i].isOn()&&board[x+i][y+i].isBlack()!=black){
			board[x+i][y+i].Reverse();
			count[black]++;
			count[!black]--;
			successfullyPut++;
		}
		else{
			broke++;
			break;
		}
	}
	if(broke&&!board[x+i][y+i].isOn()){
		broke--;
		for(i--; i>0; i--){
			board[x+i][y+i].Reverse();
			count[black]--;
			count[!black]++;
			successfullyPut--;
		}
	}





	for(i=1; ;i++){
		if(board[x-i][y+i].isOn()&&board[x-i][y+i].isBlack()!=black){
			board[x-i][y+i].Reverse();
			count[black]++;
			count[!black]--;
			successfullyPut++;
		}
		else{
			broke++;
			break;
		}
	}
	if(broke&&!board[x-i][y+i].isOn()){
		broke--;
		for(i--; i>0; i--){
			board[x-i][y+i].Reverse();
			count[black]--;
			count[!black]++;
			successfullyPut--;
		}
	}

	for(i=1; ;i++){
		if(board[x+i][y-i].isOn()&&board[x+i][y-i].isBlack()!=black){
			board[x+i][y-i].Reverse();
			count[black]++;
			count[!black]--;
			successfullyPut++;
		}
		else{
			broke++;
			break;
		}
	}
	if(broke&&!board[x+i][y-i].isOn()){
		broke--;
		for(i--; i>0; i--){
			board[x+i][y-i].Reverse();
			count[black]--;
			count[!black]++;
			successfullyPut--;
		}
	}



	for(i=1; ;i++){
		if(board[x-i][y-i].isOn()&&board[x-i][y-i].isBlack()!=black){
			board[x-i][y-i].Reverse();
			count[black]++;
			count[!black]--;
			successfullyPut++;
		}
		else{
			broke++;
			break;
		}
	}
	if(broke&&!board[x-i][y-i].isOn()){
		broke--;
		for(i--; i>0; i--){
			board[x-i][y-i].Reverse();
			count[black]--;
			count[!black]++;
			successfullyPut--;
		}
	}

	if(successfullyPut){
		board[x][y].PutPiece(black);
		count[black]++;
	}
	
	return successfullyPut;
}


	State getState(int x, int y){
		State result=board[x][y];
		return result;
	}

	int taken(int x, int y, bool black)
		{//returns how many more pieces there would be if a piece is put at x,y
	int tempBlack=count[BLACK];
	int tempWhite=count[WHITE];
	for(int i(0); i<10; i++){
		for(int j(0); j<10; j++){
			temp[i][j]=board[i][j];
		}
	}
	int result=PutPiece(black, x, y);
	if(result==0){
		return 0;
	}
	for(int i(0); i<10; i++){
		for(int j(0); j<10; j++){
			board[i][j]=temp[i][j];
		}
	}
	result=abs(count[BLACK]-tempBlack);
	count[BLACK]=tempBlack;

	count[WHITE]=tempWhite;
	return result;

}


	bool isLegal(int x, int y, bool black)
	{
	if(board[x][y].isOn()) return false;
	if(board[x-1][y].isOn()&&board[x-1][y].isBlack()==!black){
		for(int i(x-2); ; i--){
			if(board[i][y].isOn()){
				if(board[i][y].isBlack()==black){
					return true;
				}
			}
			else break;
		}
	}
	if(board[x+1][y].isOn()&&board[x+1][y].isBlack()==!black){
		for(int i(x+2); ; i++){
			if(board[i][y].isOn()){
				if(board[i][y].isBlack()==black){
					return true;
				}
			}
			else break;
		}
	}
	if(board[x][y-1].isOn()&&board[x][y-1].isBlack()==!black){
		for(int i(y-2); ; i--){
			if(board[x][i].isOn()){
				if(board[x][i].isBlack()==black){
					return true;
				}
			}
			else break;
		}
	}

	if(board[x][y+1].isOn()&&board[x][y+1].isBlack()==!black){
		for(int i(y+2); ; i++){
			if(board[x][i].isOn()){
				if(board[x][i].isBlack()==black){
					return true;
				}
			}
			else break;
		}
	}

	if(board[x+1][y+1].isOn()&&board[x+1][y+1].isBlack()==!black){
		for(int i(x+2), j(y+2); ; i++, j++){
			if(board[i][j].isOn()){
				if(board[i][j].isBlack()==black){
					return true;
				}
			}
			else break;
		}
	}
	if(board[x+1][y-1].isOn()&&board[x+1][y-1].isBlack()==!black){
		for(int i(x+2), j(y-2); ; i++, j--){
			if(board[i][j].isOn()){
				if(board[i][j].isBlack()==black){
					return true;
				}
			}
			else break;
		}
	}
	if(board[x-1][y+1].isOn()&&board[x-1][y+1].isBlack()==!black){
		for(int i(x-2), j(y+2); ; i--, j++){
			if(board[i][j].isOn()){
				if(board[i][j].isBlack()==black){
					return true;
				}
			}
			else break;
		}
	}
	if(board[x-1][y-1].isOn()&&board[x-1][y-1].isBlack()==!black){
		for(int i(x-2), j(y-2); ; i--, j--){
			if(board[i][j].isOn()){
				if(board[i][j].isBlack()==black){
					return true;
				}
			}
			else break;
		}
	}
	return false;

}

	int getCount(bool black){
		return count[black];
	}
	//int getBlackCount(){
	//	return count[BLACK];
	//}
	void SetState(bool black,int x,int y,bool isOn)
	{
		if(black && isOn)
		{
			board[x][y].SetBlack();
			count[BLACK]++;
		}
		else if(!black && isOn)
		{
			board[x][y].SetWhite();
			count[WHITE]++;
		}
		else if(!isOn)
			board[x][y].SetNone();
	}

private:
	State board[10][10];
	State temp[10][10];
	int count[2];
};

struct Coordinate{
	int x;
	int y;
};

class Player{
	friend class Board;
	friend class State;
public:
	Player(){
		
	}
	void Reset()
	{
		board.Reset();
	}
	void setSide(bool black){
		blackSide=black;
	}

	virtual void GetLastMove(Coordinate move, bool black){
		//for(int i(0); i<10; i++){
		//	for(int j(0); j<10; j++){
		//		board[i][j]=bd->getState(i, j);
		//	}
		//}
	}
	virtual Coordinate GetCoordinate(){
		Coordinate temp;
		temp.x=0;
		temp.y=0;
		return temp;
	}
	Board getBoard()
	{
		return board;
	}
	bool getSide()
	{
		return blackSide;
	}

	/*void SetBoard(Board bd)
	{
		for(int i(0); i<10; i++){
			for(int j(0); j<10; j++){
				board[i][j].setpieceOn(bd[i][j].getpieceOn());
				board[i][j].setcolorIsBlack(bd[i][j].getcolorIsBlack());
			}
		}
		bd.c
	}*/
	void SetBoard(Board bd)
	{
		board.copy(bd);
	}
	void copyFromPlayer(Player player2)
	{
		board.copy(player2.getBoard());
		blackSide = player2.getSide();
	}
protected:

	//State board[10][10];
	Board board;
	bool blackSide;

};
class RookiePlayer: public Player{
public:
	
	void GetLastMove(Coordinate move, bool black){
		board.PutPiece(black, move.x, move.y);
	}
	Coordinate GetCoordinate(){
		Coordinate temp;
		temp.x=0;
		temp.y=0;
		int benefit(0);
		for(int i(1); i<9; i++){
			for(int j(1); j<9; j++){
				int newBenefit=board.taken(i,j , blackSide);
				if(newBenefit>benefit){

					benefit=newBenefit;
					temp.x=i;
					temp.y=j;
				}
			}
		}
		return temp;
	}

};

int checkColor(Board board, bool black, int x, int y){
	if(board.getState(x, y).isOn()){
		if(board.getState(x,y).isBlack()==black){
			return 1;
		}
		else return -1;
	}
	return 0;
}
	
int Benefit(Board board, int layer, bool blackSide){
	int benefit;
	if(layer==0){
		benefit=0;
		

		if(!board.getState(1, 1).isOn()){
			benefit-=11*checkColor(board, blackSide, 2,2);
			benefit-=2*checkColor(board, blackSide, 1,2);
			benefit-=2*checkColor(board, blackSide, 2,1);
		}
		if(!board.getState(1, 8).isOn()){
			benefit-=11*checkColor(board, blackSide, 2,7);
			benefit-=2*checkColor(board, blackSide, 2,8);
			benefit-=2*checkColor(board, blackSide, 1,7);
		}
		if(!board.getState(8, 1).isOn()){
			benefit-=11*checkColor(board, blackSide, 7,2);
			benefit-=2*checkColor(board, blackSide, 7,1);
			benefit-=2*checkColor(board, blackSide, 8,2);
		}
		if(!board.getState(8, 8).isOn()){
			benefit-=11*checkColor(board, blackSide, 7,7);
			benefit-=2*checkColor(board, blackSide, 7,8);
			benefit-=2*checkColor(board, blackSide, 8,7);
		}


		//corners
		benefit+=13*checkColor(board, blackSide, 1,1);
		benefit+=13*checkColor(board, blackSide, 1,8);
		benefit+=13*checkColor(board, blackSide, 8,1);
		benefit+=13*checkColor(board, blackSide, 8,8);


		for(int i(3); i<7; i++){//on the edge
			benefit+=3*checkColor(board, blackSide, 1, i);
			benefit+=3*checkColor(board, blackSide, i, 1);
			benefit+=3*checkColor(board, blackSide, 8, i);
			benefit+=3*checkColor(board, blackSide, i, 8);
		}

		for(int i(3); i<7; i++){//on the edge
			benefit-=1*checkColor(board, blackSide, 2, i);
			benefit-=1*checkColor(board, blackSide, i, 2);
			benefit-=1*checkColor(board, blackSide, 7, i);
			benefit-=1*checkColor(board, blackSide, i, 7);
		}

	}
	else if(layer%2){
		benefit=-1000;
		for(int i(1); i<9; i++){
			for(int j(1); j<9; j++){
				if(board.isLegal(i, j, !blackSide)){
					Board temp=board;
					temp.PutPiece(blackSide, i, j);
					int tempBenefit=Benefit(temp, layer-1, blackSide);
					if(tempBenefit>benefit){
						benefit=tempBenefit;
					}
				}
			}
		}
	}
	else{
		benefit=1000;
		for(int i(1); i<9; i++){
			for(int j(1); j<9; j++){
				if(board.isLegal(i, j, !blackSide)){
					Board temp=board;
					temp.PutPiece(!blackSide, i, j);
					int tempBenefit=Benefit(temp, layer-1, blackSide);
					if(tempBenefit<benefit){
						benefit=tempBenefit;
					}
				}
			}
		}
	}
	return benefit;



}
	

class MediumPlayer: public Player{
public:
	void GetLastMove(Coordinate move, bool black){
		board.PutPiece(black, move.x, move.y);
	}
	
	Coordinate GetCoordinate(){
		int benefit(-11111);
		Coordinate move;
		move.x=0;
		move.y=0;
		for(int i(1); i<9; i++){
			for(int j(1); j<9; j++){
				if(board.isLegal(i, j, blackSide)){
					Board temp=board;
					temp.PutPiece(blackSide,i, j );
					int tempBenefit=Benefit(temp, 4, blackSide);
					if(tempBenefit>benefit){
						benefit=tempBenefit;
						move.x=i;
						move.y=j;
					}
				}
			}
		}
		return move;
	}
};






void Print(Board* bd, bool black){
	cout<<' ';
	for(int i(1); i<9; i++){
		cout<<char(i+'a'-1);
	}
	cout<<endl;

	for(int i(1); i<9; i++){
		cout<<i;
		for(int j(1); j<9; j++){
			if(bd->getState(i,j).isOn()==0){
				if(bd->isLegal(i,j, black)){
					cout<<'*';
				}
				else{
					cout<<' ';
				}
			}
			else if(bd->getState(i,j).isBlack())
				cout<<'#';
			else 
				cout<<'O';
		}
		cout<<endl;
	}
	cout<<endl<<"black : "<<bd->getCount(BLACK)<<endl;
	cout<<"white : "<<bd->getCount(WHITE)<<endl;

	cout<<endl;
}
class HumanPlayer: public Player{
	void GetBoard(Board* bd){
		//Print(bd, blackSide);
	}
	Coordinate GetCoordinate(){
		Coordinate temp;
		char b;
		cin>>temp.x>>b;
		temp.y=b-'a'+1;
		return temp;
	}
};


class Game{
public:
	Game(){
		bd=new Board();
	}
	void Run(){
		playerBlack=new MediumPlayer;
		playerWhite=new MediumPlayer;
		playerBlack->setSide(BLACK);
		playerWhite->setSide(WHITE);
		Coordinate move;
		bool blackToGo=1;
		Print(bd, blackToGo);
		while(1){
			if(blackToGo){
				move=playerBlack->GetCoordinate();
			}
			else{
				move=playerWhite->GetCoordinate();
			}
			if(move.x==0){

				cout<<"No spot available for "<<(blackToGo? "black" :"white")<<endl;
				blackToGo=!blackToGo;
				continue;
			}
			bd->PutPiece(blackToGo, move.x, move.y);
			cout<<move.x<<' '<<char(move.y+'a'-1)<<endl;
			playerBlack->GetLastMove(move, blackToGo);
			playerWhite->GetLastMove(move, blackToGo);
			blackToGo=!blackToGo;

			Print(bd, blackToGo);

			if(bd->getCount(WHITE)==0){
				cout<<"Black wins"<<endl;
				break;
			}
			if(bd->getCount(BLACK)==0){
				cout<<"White wins"<<endl;
				break;
			}
			if(bd->getCount(BLACK)+bd->getCount(WHITE)==64){
				if(bd->getCount(BLACK)>bd->getCount(WHITE)){
					cout<<"Black wins"<<endl;
					break;
				}
				else if(bd->getCount(BLACK)<bd->getCount(WHITE)){
					cout<<"White wins"<<endl;
					break;
				}
				else{
					cout<<"TIES"<<endl;
					break;
				}
		}

		}
	}
private:
	Board* bd;
	Player* playerBlack;
	Player* playerWhite;
};


